The need for resource allocation decisions arises in a broad range of technological and industrial areas such as the assignment of transmission facilities in telephone transmission systems, the control of the product mix of a factory, the deployment of industrial equipment, inventory control, and others. Resource allocation in this context means, in general, the deployment of specific technological or industrial resources for the production of particular technological or industrial results.
Resource allocation decisions are typically subject to constraints on such allocations. Resources are always limited in overall availability and, furthermore, the usefulness of a particular resource in some particular application can also be limited. For example, the overall traffic offered to a telecommunications system is limited, and the traffic-carrying capacity of each individual link in the communication system is also limited. Each particular allocation of a resource can be associated with a "payoff," i.e., a cost of that allocation or an allocation benefit (e.g., profit). The problem, then, is to allocate all of the resources so as to satisfy all of the constraints and, simultaneously, to maximize the payoff, i.e., minimize the costs or maximize the benefits.
One method of representing allocation decision problems is called the linear programming model. Such a model consists of a number of linear expressions that represent the quantitative relationships between the various possible allocations, their constraints, and their costs or their benefits. The set of relationships is said to be linear if all of the relationships are sums of constant coefficients times unknown allocation values which are equal to, greater than or equal to, or less than or equal to, a constant. Many resource allocation problems, of course, cannot be represented by such linear relationships, but involve higher powers of the unknowns or other nonlinearities in the relationships and hence are not susceptible to linear programming approaches.
It should be noted that the resource allocation problems discussed above are real physical problems arising in real physical systems. While it is true that significant quantitative aspects of the physical problem can be represented by the linear programming model, the purpose of this model is to provide optimum values which are then used in the physical world to construct or operate a physical system. Typical prior art examples of the use of such mathematical models to characterize physical systems are the use of equations to construct radio antennas or to control rubber-molding operations.
At one time, many of the resource allocation problems described above were solved by human beings using their intuition and experience. More recently, quantitative tools such as statistics, modeling, graphs and linear programming have become available to assist human beings in these decision-making activities. For example, manufacturing plants use linear programming models to control production schedules and inventory levels that will satisfy sales demands and, at the same time, minimize production and inventory costs. Similarly, a communication system uses linear programming models to route telephone traffic over a network of transmission facilities so that the entire traffic demand is satisfied, no transmission links are overloaded, and transmission costs are minimized.
The best known prior art approach to solving allocation problems posed as linear programming models is known as the simplex method, invented by George B. Danzig in 1947, and described in Linear Programming and Extensions, by George B. Danzig, Princeton University Press, Princeton, New Jersey, 1963. In accordance with the simplex method, the first step is to select an initial feasible allocation as a starting point, possibly by using another linear programming model which is a variant of the original model. A feasible allocation, in this regard, is one which satisfies all of the constraints, but which is not known to be optimal. Successive new allocations are thereafter identified which improve the function to be optimized (called the objective function). The above process is repeated iteratively, selecting new tentative allocations which are always closer to the optimum allocation. This iterative process stops when the current tentative allocation can no longer be improved.
The simplex method may be better understood by considering the simplified graphical representation of a linear programming model given in FIG. 1. In FIG. 1, there is shown a three-dimensional representation of a convex polytope 10 having a plurality of facets, such as facet 11. Each of the facets of polytope 10 is a graphical representation of a portion of one of the constraint relationships in the formal linear programming model. That is, each linear constraint defines a plane in the space of the polytope 10, and a portion of that plane forms a facet of the polytope 10. Polytope 10 is convex in the sense that a line joining any two points on the surface of the polytope 10 lies within polytope 10.
It should be noted that polytope 10 is shown as a three-dimensional polygon for illustrative purposes only. In fact, the polytope representation of a linear programming model is contained in a hyperspace having a number of dimensions equal to the number of unknown allocation values (when viewed as in FIG. 1) or, more precisely, the number of inequality constraint relationships minus the number of equality constraint relationships. Indeed, the polytope divides the hyperspace into the feasible region of polytope 10 and the infeasible region outside of polytope 10.
It is well known that optimum resource allocations in linear programming models lie at vertices of polytope 10. In some models, an entire edge or an entire facet of polytope 10 will represent optimum allocations, and hence more than one vertex may be optimal. The strategy of the simplex method is to successively identify adjacent vertices of polytope 10, where each new vertex (each representing a new feasible set of allocations) is closer, as measured by the objective function, to the optimum point 21 than was the previous allocation. In FIG. 1, the simplex method might first identify vertex 12 and then move in a path 13 from vertex to vertex (14 through 20) until arriving at the optimum point 21. The simplex method is thus constrained to move on the surface of polytope 10 and, moreover, to move from one vortex 12 of polytope 10 to an adjacent vertex (e.g., 14). In large linear programming problems, involving thousands, hundreds of thousands, or even millions of variables, the number of vertices on the polytope increases correspondingly, sometimes exponentially. The length of path 13 increases, on the average, in direct proportion to the number of variables. Moreover, there are so-called "worst case" problems where the topology of the polytope is such that a substantial fraction of the vertices must be traversed to reach the optimum vertex.
As a result of these and other factors, the average computation time needed to solve a linear programming model by the simplex method grows at least proportionally to the square of the number of constraints in the model. For even moderately-sized allocation problems, this time is often so large that using the model is not practical, i.e., the constraints change before an optimum allocation can be computed, or the computation time necessary to optimize allocations using the model (presumably on a computer) is so large that it is simply not available for that purpose at a reasonable cost. Optimum allocations could not generally be made in "real time," i.e., sufficiently fast to provide more or less continuous control of an ongoing process, system or apparatus.
A second method for attacking linear programming models has been called the ellipsoid method, invented by N. Z. Shor of the Soviet Union in 1970, and described in an article by L. G. Khachiyan, "A Polynomial Algorithm in Linear Programming," Doklady Akademiia Nauk SSSR 244:S, pp. 1093-1096, 1979 (translated in 20 Soviet Mathematics Doklady 1, pp. 191-94, 1979). In the ellipsoid method, the polytope 30 of FIG. 2 is enclosed in an ellipsoid 31 having a center point 32. The center point 32 of ellipsoid 31 is checked to see if it is inside or outside of polytope 30. If point 32 is outside the polytope 30, as shown in FIG. 2, a plane 33 is passed through the center point 32 parallel to a facet of polytope 30 such that point 32 is on the wrong side (outside) of the constraint containing that facet. It is then determined which half of ellipsoid 31 contains polytope 30. In FIG. 2, it is the upper half of ellipsoid 30.
A second, smaller ellipsoid 34 is then constructed around the upper half of ellipsoid 31, having a center point 35. Again, center point 35 is checked to see if it is inside or outside of polytope 30. If it is outside (as in FIG. 2), the above process is repeated until the center point is within polytope 30. When the center point of the enclosing ellipsoid is within the polytope 30, the plane through the center point is drawn normal to the direction of the objective function to cut the polytope 30 into two pieces. It is then determined which piece of polytope 30 contains the optimum point 36. Another ellipsoid is then constructed around the half of polytope 30 containing the optimum point 36, another plane is passed through its center, a test performed to identify which half of the ellipsoid contains the optimum point 36, and so forth. This process is continued until the center point more or less coincides with the optimum point 36. The coordinates of the center point can then be "rounded" to the exact values of the optimum allocations represented by point 36 within the accuracy of the numbering system used to express the model in the first instance.
Although conceptually very simple, the ellipsoid method performs more slowly than the simplex method for most linear programming models for reasons discussed by R. G. Bland et al. in "The Ellipsoid Method: A Survey," Operations Research, Vol. 29, No. 6 (1981), pp. 1039-1091.
A new and more efficient method or procedure for attacking linear programming models is needed. For example, the optimum routing of long haul telephone traffic through the national telephone network involves a very large number of possible linkages, all with associated costs and constraints. Solutions to this particular problem must be available within a reasonable time, i.e., a time short enough so that practical use can be made of that solution by adjusting the traffic routing so as to take advantage of the optimum values. It is the solution of this type of problem to which the present invention is directed.